package main

import (
	"fmt"
	"time"
)

func main() {
	// sortMain()
	findMain()
}

func sortMain() {
	var startTime int64
	var endTime int64
	var arr [5]int = [...]int{24, 69, 80, 57, 13}
	var slice []int = []int{24, 69, 80, 57, 13}

	fmt.Println("数组：")
	startTime = time.Now().UnixNano()
	bubbleSortingArray(&arr)
	endTime = time.Now().UnixNano()
	fmt.Println("结果为", arr)
	fmt.Println("耗时", endTime-startTime)

	fmt.Println("切片：")
	fmt.Println("循环：")
	startTime = time.Now().UnixNano()
	bubbleSortingSliceFor(slice)
	endTime = time.Now().UnixNano()
	fmt.Println("结果为", slice)
	fmt.Println("耗时", endTime-startTime)
	fmt.Println("递归：")
	startTime = time.Now().UnixNano()
	bubbleSortingSlice(slice)
	endTime = time.Now().UnixNano()
	fmt.Println("结果为", slice)
	fmt.Println("耗时", endTime-startTime)
}

func findMain() {
	//var arr1 [4]string = [...]string{"老鹰", "狮子", "龙", "蝙蝠"}
	//sequentialFind(&arr1)

	var arr2 []int = []int{1, 3, 4, 5, 6, 8, 9, 45}
	fmt.Println(binaryFind(arr2, 0, len(arr2)-1, 45))
}

func bubbleSortingSlice(slice []int) {
	// 递归写法
	var flag bool = false
	for i := 0; i < len(slice)-1; i++ {
		if slice[i] > slice[i+1] {
			slice[i], slice[i+1] = slice[i+1], slice[i]
			flag = true
		}
	}
	if flag {
		bubbleSortingSlice(slice)
	}
}

func bubbleSortingSliceFor(slice []int) {
	// 循环写法
	for i := len(slice) - 1; i > 0; i-- {
		for j := 0; j < len(slice)-1; j++ {
			if slice[j] > slice[j+1] {
				slice[j], slice[j+1] = slice[j+1], slice[j]
			}
		}
	}
}

func bubbleSortingArray(arr *[5]int) {
	// 双重循环写法
	for i := len(arr) - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func sequentialFind(arr *[4]string) {
	//有一个数列 老鹰、狮子、龙、蝙蝠，
	//从键盘中任意输入一个名字，判断数列中是否包含此名称（顺序查找）
	var index = -1
	var name string
	fmt.Println("请输入要查找的名称.....")
	fmt.Scanln(&name)
	for i, str := range arr {
		if str == name {
			index = i
			break
		}
	}
	if index != -1 {
		fmt.Printf("找到了 %v， 下标为 %d\n", name, index)
	} else {
		fmt.Printf("没有找到 %v\n", name)
	}
}

func binaryFind(arr []int, leftIndex int, rightIndex int, findVal int) (index int) {
	if leftIndex > rightIndex {
		return -1
	}
	var middleIndex = (leftIndex + rightIndex) / 2
	if arr[middleIndex] > findVal {
		index = binaryFind(arr, leftIndex, middleIndex-1, findVal)
	} else if arr[middleIndex] < findVal {
		index = binaryFind(arr, middleIndex+1, rightIndex, findVal)
	} else if arr[middleIndex] == findVal {
		index = middleIndex
	}
	return
}
